package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-03-11 23:51
 **/
public class LeetCode2049 {

    //节点个数
    int n;
    //最高得分
    long maxScore;
    //最高得分的个数
    int cnt;
    List<Integer>[] children;

    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        children = new List[n];
        for (int i = 0; i < n; i++) {
            children[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            int p = parents[i];
            if (p != -1) {
                children[p].add(i);
            }
        }
        dfs(0);
        return cnt;
    }

    int dfs(int node) {
        long  score = 1;
        //移除一个节点剩余的节点个数
        int size = n - 1;
        for (int i : children[node]) {
            //t: 分支的节点个数
            int t = dfs(i);
            //乘以当前分支的分数
            score *= t;
            //减去当前分支的节点个数
            size -= t;
        }

        //如果不是根节点,分数还要乘上除去左右分支以及当前节点的剩余节点个数
        if (node != 0) {
            score *= size;
        }

        if (score == maxScore) {
            ++cnt;
        } else if (score > maxScore) {
            maxScore = score;
            cnt = 1;
        }

        //返回当前分支的节点数
        return n - size;
    }

}
